import java.util.*;
public class FindSmallestInteger {
  public int findSmallestInteger(int[] nums, int value) {
    // 统计每个余数出现的次数
    Map<Integer, Integer> remainderCount = new HashMap<>();
    
    for (int num : nums) {
        // 处理负数余数，确保得到非负数余数
        int remainder = ((num % value) + value) % value;
        remainderCount.put(remainder, remainderCount.getOrDefault(remainder, 0) + 1);
    }
    
    // 从0开始查找最小缺失的非负整数
    int mex = 0;
    while(true){
        int currentRemainder = mex % value;
        // 如果当前余数还有剩余计数，则可以通过操作得到mex
        if (remainderCount.getOrDefault(currentRemainder, 0) > 0) {
            // 使用了一个该余数的元素，减少计数
            remainderCount.put(currentRemainder, remainderCount.get(currentRemainder) - 1);
            mex++;
        } else {
            // 无法得到当前mex，返回mex
            break;
        }
    }
    
    return mex;
  }

  public static void main(String[] args) {
    FindSmallestInteger fsi = new FindSmallestInteger();
    int[] nums = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int value = 4;
    int result = fsi.findSmallestInteger(nums, value);
    System.out.println(result);
  }
}


// 给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

// 在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

// 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。
// 数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

// 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。
// 返回在执行上述操作 任意次 后，nums 的最大 MEX 。

 

// 示例 1：

// 输入：nums = [1,-10,7,13,6,8], value = 5
// 输出：4
// 解释：执行下述操作可以得到这一结果：
// - nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
// - nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
// - nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
// nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。
// 示例 2：

// 输入：nums = [1,-10,7,13,6,8], value = 7
// 输出：2
// 解释：执行下述操作可以得到这一结果：
// - nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
// nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。